#include <iostream>
#include <cmath>
#include <cstdlib>
#include <string>

using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
};

int max(int a, int b) {
	return a > b ? a : b;
}

void output(string s) {
    char res[26];
    int index = 0;
    int i;
    for (i = 0; i < s.length(); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z')
            res[index++] = s[i];
    }
    
    for (i = 0; i < index - 1; i++) {
        cout << res[i] << ",";
    }
    cout << res[index - 1] << endl;
}

string preOrder(string s, int pos) {
    string l = "";
    string r = "";
    if (2 * pos <= s.length()) l = preOrder(s, pos * 2);
    if (2 * pos <= s.length()) r = preOrder(s, pos * 2 + 1);
    return s[pos - 1] + l + r;
}

string inOrder(string s, int pos) {
    string l = "";
    string r = "";
    if (2 * pos <= s.length()) l = inOrder(s, pos * 2);
    if (2 * pos <= s.length()) r = inOrder(s, pos * 2 + 1);
    return l + s[pos - 1] + r;
}

string sufOrder(string s, int pos) {
    string l = "";
    string r = "";
    if (2 * pos <= s.length()) l = sufOrder(s, pos * 2);
    if (2 * pos <= s.length()) r = sufOrder(s, pos * 2 + 1);
    return l + r + s[pos - 1];
}

string sufOrder(Node* node) {
    if (node == NULL || node->val == -1) return "";
    string l = sufOrder(node->left);
    string r = sufOrder(node->right);
    return l + r + (char)node->val;
}

char tmp[100];
int maxIndex = 0;
void levelOrder(Node* node, int index) {
    if (node != NULL) {
        tmp[index] = node->val;

		maxIndex = max(index, maxIndex);

        levelOrder(node->left, index * 2);
        levelOrder(node->right, index * 2 + 1);
    }
}

void task1(string s) {
    output(preOrder(s, 1));
    output(inOrder(s, 1));
    output(sufOrder(s, 1));
    cout << s.length() << endl;

    int dep = log(s.length()) / log(2);
    cout << dep + 1 << endl;
}

int indexOf(string s, char c) {
    for (int i = 0; i < s.length(); i++)
        if (s[i] == c) return i;
    return -1;
}

int level = 0;
Node* buildTree(string pre, string ins, int l, int r) {
    if (l > r || r < l) return NULL;
    if (l == r) {
        Node* node = new Node();
        node->val = pre[level++];
        node->left = NULL;
        node->right = NULL;
        return node;
    }

    Node* rootNode = new Node();
    char root = pre[level++];
    rootNode->val = root;
    rootNode->left = buildTree(pre, ins, l, indexOf(ins, root) - 1);
    rootNode->right = buildTree(pre, ins, indexOf(ins, root) + 1, r);
    return rootNode;
}

void task2(string pre, string ins) {
    Node* tree = buildTree(pre, ins, 0, ins.length() - 1);
    output(sufOrder(tree));
    levelOrder(tree, 1);

	string ts = "";
	int i;
    for (i = 1; i <= maxIndex; i++) {
		if (tmp[i] >= 'A' && tmp[i] <= 'Z') ts += tmp[i];
    }
    for (i = 0; i < ts.length() - 1; i++) cout << ts[i] << ",";
	cout << ts[ts.length() - 1] << endl;
}

int main() {
    string s;
    cout << "Input1" << endl;
    cin >> s;
    cout << "Output1" << endl;
    task1(s);
    cout << "Input2" << endl;
    string pre;
    string ins;
    cin >> pre; cin >> ins;
    cout << "Output2" << endl;
    task2(pre, ins);
    cout << "End" << endl;
    return 0;
}